Bajtlantydzkie miasta [B]

Limit pamięci: 64 MB

"Odcinek jest najkrótszą drogą łączącą dwa punkty" - to hasło było główną motywacją dla projektantów dróg w Cesarstwie Bajtlantydy. Z tego powodu wszystkie budowane tam drogi były proste i prowadziły przez cały kraj. W każdym miejscu, w którym krzyżowały się dwie drogi, Bajtlantydzi zakładali miasto. Aby uniknąć nieporozumień, Bajtlantydzi nigdy nie prowadzili więcej niż dwóch dróg przez jeden punkt.

Cesarz Bajtlantydy chce teraz podzielić swoje państwo na dwie prowincje, w miarę możliwości równe pod względem liczby miast. Granicą prowincji zamierza ustanowić jedną z dróg Cesarstwa. Miasta na drodze granicznej nie będą podlegać żadnej z prowincji, ale bezpośrednio Cesarzowi. Cesarz chciałby sprawdzić, dla każdej drogi, jaka jest wartość bezwzględna różnicy między liczbami miast po jednej i po drugiej stronie tej drogi.

Bajtazar, nadworny kartograf, spędził wiele dni, wykonując polecenie dane mu przez Cesarza. Twoim zadaniem jest napisanie programu, który pomoże mu w pracy.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się liczba całkowita (), oznaczająca liczbę dróg w Cesarstwie. W kolejnych wierszach znajdują się opisy poszczególnych dróg w postaci czwórek liczb całkowitych , , , (, punkty i nie pokrywają się), pooddzielanych pojedynczymi odstępami. Każda taka czwórka opisuje jedną drogę, która jest prostą przechodzącą przez punkty i . Żadne dwie drogi nie pokrywają się. Żadne trzy drogi nie przecinają się w jednym punkcie. Zakładamy, że Cesarstwo jest na tyle duże, że wszystkie przecięcia prostych wyznaczających drogi leżą w jego granicach.

Wyjście

Na standardowe wyjście wypisz wierszy, zawierających odpowiedzi dla dróg podanych na wejściu (w tej samej kolejności). Odpowiedzią dla danej drogi jest wartość bezwzględna różnicy liczby miast po jej dwóch stronach.

Przykład

Dla danych wejściowych:

4
1 -1 1 10
0 0 1 0
2 0 2 1
4 4 -1 -1

poprawną odpowiedzią jest:

1
2
3
2

W tym przykładzie mamy pięć miast o współrzędnych , , , i .

Autor zadania: Jakub Onufry Wojtaszczyk.